package main;

    /**
     * 快速排序：Java
     *
     * @author skywang
     * @date 2014/03/11
     */
    public class QuiteSort {
        /*
         * 快速排序
         *
         * 参数说明：
         *     a -- 待排序的数组
         *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
         *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
         */
        /*
         * 快速排序
         *
         * 参数说明：
         *     a -- 待排序的数组
         *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
         *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
         */
        static void quick_sort(int a[], int l, int r)
        {
            if (l < r)
            {
                int i,j,x;

                i = l;
                j = r;
                x = a[i];
                while (i < j)
                {
                    while(i < j && a[j] > x)
                        j--; // 从右向左找第一个小于x的数
                    if(i < j)
                        a[i++] = a[j];
                    while(i < j && a[i] < x)
                        i++; // 从左向右找第一个大于x的数
                    if(i < j)
                        a[j--] = a[i];
                }
                a[i] = x;
                quick_sort(a, l, i-1); /* 递归调用 */
                quick_sort(a, i+1, r); /* 递归调用 */
            }
        }


        public static void main(String[] args) {

            int [] a =  {30, 40, 60, 10, 20, 50};
//            QuietSort(a,0,a.length-1);
//
//            for (int i : a) {
//                System.out.println(i);
//            }

            QuietSort(a,0,a.length-1);
                        for (int i : a) {
                System.out.println(i);
            }

        }

        // 改进成方法

        public static  void QuietSort(int [] a, int l, int r  ){

            int left = l;
            int right = r;
            int cur = a[left];

            if( l< r) {


                while (left < right) {

                    while (left < right && a[right] > cur) {
                        right--;
                    }
                    if (left < right) {
                        a[left] = a[right];
                        // 之后从 左向 右 找 所以 left  需要++；
                        left++;
                    }
                    // 从右边找到 大于  基准数的
                    while (left < right && a[left] < cur) {
                        left++;
                    }
                    if (left < right) {
                        a[right] = a[left];
                        right--;
                    }

                    a[left] = cur;

                    // 递归
                    QuietSort(a, l, left - 1);
                    QuietSort(a, left + 1, r);

                }

            }
            System.out.println("l:"+l);
            System.out.println("left:"+left);
            System.out.println("r:"+r);


        }




        public static void swap( int [] a,int i,int j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }

}
